package offer;

import javax.sound.midi.Soundbank;
import java.util.PriorityQueue;

public class offer59_I {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {1,3,-1,-3,5,3,6,7};
        solution.maxSlidingWindow(nums,3);
    }


    static class Solution {
        public int[] maxSlidingWindow(int[] nums, int k) {
            int len = nums.length;
            int[] arr = new int[len-k+1];
            PriorityQueue<int[]> queue = new PriorityQueue<>((p1, p2) -> p1[0] == p2[0] ? p2[1] - p1[0] : p2[0] - p1[0]);
            for(int i = 0; i< k; i++){
                queue.offer(new int[]{nums[i],i});
            }
            arr[0] = queue.poll()[0];
            for(int i = k; i < len; i++){
                queue.offer(new int[]{nums[i],i});
                while(queue.peek()[1] <= i-k){
                    queue.poll();
                }
                arr[i-k+1] = queue.peek()[0];
            }
            return arr;
        }
    }
}
